#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

struct poly {
    list_t node;
    int coef;
    int exp;
};
typedef struct poly poly_t;


void polyAdd(poly_t *A, poly_t *B, poly_t *C) {
    poly_t *nodeA = (poly_t*)A->node.next;
    poly_t *nodeB = (poly_t*)B->node.next;
    while(nodeA!=A || nodeB!=B) {
        poly_t *node = (poly_t *) malloc(sizeof(poly_t));
        if (nodeA==A) {
            node->coef = nodeB->coef;
            node->exp = nodeB->exp;
            nodeB = (poly_t*)nodeB->node.next;
        } else if (nodeB == B) {
            node->coef = nodeA->coef;
            node->exp = nodeA->exp;
            nodeA = (poly_t*)nodeA->node.next;
        } else {
            if (nodeA->exp == nodeB->exp) {
                node->coef = nodeA->coef + nodeB->coef;
                node->exp = nodeA->exp;
                nodeA = (poly_t*)nodeA->node.next;
                nodeB = (poly_t*)nodeB->node.next;
            } else if (nodeA->exp > nodeB->exp) {
                node->coef = nodeA->coef;
                node->exp = nodeA->exp;
                nodeA = (poly_t*)nodeA->node.next;
            } else { //nodeA->exp < nodeB->exp
                node->coef = nodeB->coef;
                node->exp = nodeB->exp;
                nodeB = (poly_t*)nodeB->node.next;
            }
        }
        // add to C
        list_add_tail((list_t*)node, (list_t *) C);
    }
}

void printPoly(poly_t *C) {
    poly_t *nodeC = (poly_t*)C->node.next;
    while(nodeC != C) {
        char plus = '+';
        if (nodeC->coef < 0) plus = ' ';
        printf("%c%dX^%d", plus, nodeC->coef, nodeC->exp);
        nodeC = (poly_t *) nodeC->node.next;
    }
    printf("\n");
}

int main() {
    int polyA[3][2] = {{2,2},{4,1},{3,0}};
    int polyB[3][2] = {{3,3}, {-4,1},{-1,0}};

    poly_t A;
    poly_t B;
    poly_t C;
    
    initList((list_t *) &A);
    initList((list_t *) &B);
    initList((list_t *) &C);
    

    for (int i=0; i<3;i++) {
        poly_t *node = (poly_t *) malloc(sizeof(poly_t));
        memset(node,0,sizeof(poly_t));
        node->coef = polyA[i][0];
        node->exp = polyA[i][1];
        list_add_tail((list_t*)node, (list_t *) &A);
    }

    for (int i=0; i<3;i++) {
        poly_t *node = (poly_t *) malloc(sizeof(poly_t));
        memset(node,0,sizeof(poly_t));
        node->coef = polyB[i][0];
        node->exp = polyB[i][1];
        list_add_tail((list_t*)node, (list_t *) &B);
    }

    polyAdd((poly_t *) &(A.node.next), (poly_t*) &B.node.next, &C);
    printPoly(&C);
}